package com.jietuo.class04;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/5
 * @description:
 */
public class Code01_Heap1 {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 85, 4, 67, 23, 33, 33, 87};
        MyMaxHeap myMaxHeap = new MyMaxHeap(arr.length);
        for (int i = 0; i < arr.length; i++) {
            myMaxHeap.put(arr[i]);
        }
        while (!myMaxHeap.isEmpty()) {
            System.out.println(myMaxHeap.pop());
        }
    }

    public static class MyMaxHeap {
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit) {
            this.limit = limit;
            heap = new int[limit];
            heapSize = 0;
        }


        public boolean isEmpty() {
            return heapSize == 0;
        }

        public boolean isFull() {
            return heapSize == limit;
        }

        public void put(int value) {
            // 加入的时候，需要判断是否需要往下沉
            // 即需要和自己的左右叶子比较，左右叶子
            if (isFull()) {
                throw new RuntimeException("堆已满");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }

        public int pop() {
            // 弹出一个，那么heapSize -1 ，将heapSize上的数和头位子交换，做heapify,向下落
            int value = heap[0];
            // 需要将heapSize前一个位子和0位置交换
            swap(heap, 0, --heapSize);
            heapIfy(heap, 0, heapSize);
            return value;
        }

        private void heapIfy(int[] heap, int index, int heapSize) {
            int left = index * 2 + 1;
            // 先拿出两个子的，较大的交换
            while (left < heapSize) {
                int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
                largest = heap[largest] > heap[index] ? largest : index;
                if (largest == index) {
                    break;
                }
                swap(heap, index, largest);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private void heapInsert(int[] heap, int index) {
            // 先找到size位置的父节点 (i-1)/2
            while (heap[index] > heap[(index - 1) / 2]) {
                // 则进行交换
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int[] heap, int i, int j) {
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }
    }


}
